1. Field of the Invention
The present invention is generally related to the field of data communications, and more particularly, to the arbitration of access among plural bidding devices which communicate with a central device.
2. State of the Art
Communication systems are known wherein a central unit, commonly referred to as a hub, is connected via a communication link with one or more remote units. The communication link can, for example, be a frequency modulated radio link using a radio access protocol (RAP).
Because the plural remote units cannot all communicate with the hub at the same time, various arbitration techniques have been developed for arbitrating their access to the central unit. One known arbitration technique is the slotted reservation ALOHA protocol which was developed at the University of Hawaii several decades ago. The slotted reservation ALOHA protocol arbitrates access among plural remote units to the hub by allocating a small portion of the overall system throughput to small time windows referred to as "bid slots". The remote units use the bid slots to transmit short bid packets to the hub. Each bid packet merely represents a request to reserve larger time slots in the future for actual data packet transmission. By supplying relatively short bid packets to the hub from each of the remote units, the hub can organize future allocation of the communication link among the various remote units to provide efficient transmission of information over the communication link.
The use of bid slots to reserve future data transmission time slots pursuant to the slotted reservation ALOHA protocol eliminates the possibility of two remote units attempting to transmit data packets at the same time. The collision of data packets, which results in the waste of an entire data transmission time is thereby avoided. However, because the remote units can transmit their short bid packets at the same time, a collision of bid packets can occur.
The potential for colliding bid packets can result in remote units which are physically located at a distance from the hub never being heard by the hub. For example, in wireless links, remote units which are physically located closer to the hub typically overwhelm the transmissions from remote units which are physically located at a distance from the hub, thereby causing shadow zones of remote units whose bids cannot be serviced equitably. Consequently, if a remote unit which is located next to the hub transmits a bid packet at the same time a remote unit physically located at a distance from the hub transmits a bid packet, only the bid packet from the closer remote unit will be heard by the hub. Although a collision should have occurred thereby requiring both remote units to retransmit their bid packets, in actuality, the closer remote unit will be heard and serviced to the exclusion of the more distant remote unit. Thus, over a period of time, closer remote units will be heard on a more regular basis than remote units located at a distance from the hub.
The effect of collisions in communication networks, and in particular, wireless communication networks, has been addressed with numerous modifications to the slotted reservation ALOHA protocol technique. One technique for addressing the occurrence of collisions is to configure the hub to detect bid collisions and take unilateral action to attempt to ensure a fairness in bidding among all remote units. For example, when the frequency of bid collisions nears a predetermined value, the hub can be configured to take action. One such action might be the addition of more bid slots to the protocol overhead. Alternately, the hub could dynamically switch to a more "polled" style of operation in which the hub initiates communication with the remote units. However, such unilateral actions by the hub, in which the true success rates of individual launch pads are not taken into account, usually result in significant losses in overall system efficiency.
A second technique for addressing the occurrence of collisions in a communications network is to provide peer carrier sensing at the remote units. In accordance with this technique, each remote unit's bid transmission is preceded by an attempt to detect simultaneous transmission by another remote unit. If an impending collision is detected, the later bidder defers transmission to another bid slot to avoid the collision. This technique, while reducing the potential for collisions, requires enhanced complexity at each of the remote units and imposes a delay on bid transmission, thereby degrading efficiency since each remote unit must independently monitor the communication network before transmitting a bid packet.
A third known technique for addressing the occurrence of collisions in a wireless communications network is the use of variable transmit power among each of the remote units. In accordance with this technique, each remote unit can alter its transmit power level when faced with an inability to be heard at the hub. Using this technique, remote units located far from the hub, or shadowed units, can be heard by the hub despite the typical dominance of remote units located in closer proximity to the hub. However, this technique requires increased complexity of the remote units to provide the ability to vary their transmit power.
Thus, while techniques are known for arbitrating access among plural bidding devices vying for access to a central device in a communications link, these techniques do not effectively address the occurrence of bid collisions without significantly degrading overall operating efficiency.